// 后序 遍历

// 输入: [1,null,2,3]  
//    1
//     \
//      2
//     /
//    3 
// 输出: [null, 3, 2, 1]

import {Tree} from "./base-tree.js"

let t =new Tree();
t.insert(1);
t.insert(null);
t.insert(2);
t.insert(3);
console.log(t);

// 递归算法
let recursionPostorderTraversal = function(root,array =[]){
    if (root) {
        recursionPostorderTraversal(root.left, array);
        recursionPostorderTraversal(root.right, array);
        array.push(root.data);
      }
      return array;
}
console.log(recursionPostorderTraversal(t.root));

let iteratePostorderTraversal = function (root) {
    const result = [];
    const stack = [];
    let last = null; // 标记上一个访问的节点
    let current = root;
    while (current || stack.length > 0) {
      while (current) {
        stack.push(current);
        current = current.left;
      }
      current = stack[stack.length - 1];
      if (!current.right || current.right == last) {
        current = stack.pop();
        result.push(current.data);
        last = current;
        current = null; // 继续弹栈
      } else {
        current = current.right;
      }
    }
    return result;
  }

console.log(iteratePostorderTraversal(t.root));